/*
* 二分查找
*/


//二分查找
//https://leetcode.cn/problems/binary-search/submissions/
// class Solution {
// public:
//     int search(vector<int>& nums, int target) {
//         int left = 0, right = nums.size() - 1;

//         while (left <= right)
//         {
//             //(right - left)/2求出当前left和right区间的一半长度 加上left就是当前从0开始 left和right的中间长度
//             int mid = left + (right - left)/2; //防止溢出
//             if (nums[mid] < target) left = mid + 1;
//             else if (nums[mid] > target) right = mid - 1;
//             else return mid;
//         }
//         return -1;
//     }
// };


//在排序数组中查找元素的第一个和最后一个位置
//https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/
// class Solution {
// public:
//     vector<int> searchRange(vector<int>& nums, int target) {
//         if (nums.size() == 0) return { -1,-1 };

//         int n = nums.size();
//         int left = 0, right = n - 1;

//         //找左端点
//         while (left < right) //不能left <= right 因为最终情况是 left == right 就找到了左端点
//         {
//             //不能left+(right-left+1)/2; 因为我们需要端点向左靠 如果+1则陷入死循环
//             int mid = left + (right - left) / 2;
//             if (nums[mid] < target) left = mid + 1;
//             else right = mid;//不能mid-1 因为可能mid接近目标值 nums[mid]>=target
//         }
//         if (nums[left] != target) return { -1,-1 };
//         int begin = left;
//         right = n - 1; //重置指针

//         //找右端点
//         while (left < right)
//         {
//             //不能left+(right-left)/2; 因为我们需要端点向右靠 如果不+1则陷入死循环
//             int mid = left + (right - left + 1) / 2;
//             if (nums[mid] <= target) left = mid;//不能mid+1 因为可能mid正好是目标值
//             else right = mid - 1; //此时mid下一定是>targer的值 可以跳过 nums[mid]<=target
//         }
//         return { begin,left };
//     }
// };


//搜索插入位置
//https://leetcode.cn/problems/search-insert-position/
// class Solution {
// public:
//     int searchInsert(vector<int>& nums, int target) {
//         int n = nums.size();
//         int left = 0,right=n-1;
//         while(left < right)
//         {
//             int mid = left + (right-left)/2;
//             //这个数只能大于等于target
//             if(nums[mid] < target) left = mid+1;
//             else right = mid;
//         }
//         //如果target比目标数大 则插入在其后面的位置(target大于数组所有的数的情况)
//         if(nums[left] < target) return left+1;
//         return left; 
//     }
// };


//x的平方根
//https://leetcode.cn/problems/sqrtx/
// class Solution {
// public:
//     int mySqrt(int x) {
//         if(x < 1) return 0;
//         //从1-x开始遍历 求平方与x是否接近
//         int left = 1,right = x;
//         while(left < right)
//         {
//             long long mid = left + (right-left+1)/2;
//             //如果中间数的平方小于等于x 则left右移动
//             if((mid*mid) <= x) left=mid;
//             else right = mid-1;
//         }
//         return left;
//     }
// };


//山脉数组的峰顶索引
//https://leetcode.cn/problems/peak-index-in-a-mountain-array/submissions/
// class Solution {
// public:
//     int peakIndexInMountainArray(vector<int>& arr) {
//         int left = 0,right = arr.size()-1;
//         while(left < right)
//         {
//             int mid = left + (right-left+1)/2;
//             if(arr[mid] > arr[mid-1]) left = mid;
//             else right = mid-1;
//         }
//         return left;
//     }
// };


//寻找峰值
//https://leetcode.cn/problems/find-peak-element/submissions/
// class Solution {
// public:
//     int findPeakElement(vector<int>& nums) {
//         int left = 0,right = nums.size()-1;
//         while(left < right)
//         {
//             int mid = left + (right-left)/2;
//             if(nums[mid] > nums[mid+1]) right = mid;
//             else left = mid+1;
//         }
//         return left;
//     }
// };


//153.寻找旋转排序数组中的最小值
//https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
// class Solution {
// public:
//     int findMin(vector<int>& nums) {
//         //可以把数组分为两部分区间 左区间的全部数字大于右边区间 两个区间严格递增
//         int n = nums.size();
//         int left = 0,right = n-1;
//         while(left < right)
//         {
//             int mid = left + (right-left)/2;
//             if(nums[mid] > nums[n-1]) left = mid+1;
//             else right = mid;
//         }
//         return nums[left];
//     }
// };


//点名
//https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/submissions/
// class Solution {
// public:
//     int takeAttendance(vector<int>& records) {
//         int n = records.size();
//         int left = 0,right = n-1;
//         while(left < right)
//         {
//             int mid = left + (right-left)/2;
//             if(records[mid] == mid) left = mid+1;
//             else right = mid;
//         }
//         return records[left]==left?left+1:left;
//     }
// };

